export class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val === undefined ? 0 : val;
        this.left = left === undefined ? null : left;
        this.right = right === undefined ? null : right;
    }
}
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
    // 创建中序遍历值到索引的映射，便于快速查找
    const inorderMap = new Map<number, number>();
    for (let i = 0; i < inorder.length; i++) {
        inorderMap.set(inorder[i], i);
    }

    // 递归构建二叉树
    return buildTreeHelper(
        preorder, 0, preorder.length - 1,
        inorder, 0, inorder.length - 1,
        inorderMap
    );
}

function buildTreeHelper(
    preorder: number[], preStart: number, preEnd: number,
    inorder: number[], inStart: number, inEnd: number,
    inorderMap: Map<number, number>
): TreeNode | null {
    // 基准情况：没有节点需要构建
    if (preStart > preEnd || inStart > inEnd) {
        return null;
    }

    // 前序遍历的第一个元素是根节点
    const rootVal = preorder[preStart];
    const root = new TreeNode(rootVal);

    // 在中序遍历中找到根节点的位置
    const rootIndex = inorderMap.get(rootVal)!;

    // 计算左子树的节点数量
    const leftTreeSize = rootIndex - inStart;

    // 递归构建左子树
    // 左子树的前序遍历范围：从preStart+1开始，长度为leftTreeSize
    // 左子树的中序遍历范围：从inStart开始，到rootIndex-1结束
    root.left = buildTreeHelper(
        preorder, preStart + 1, preStart + leftTreeSize,
        inorder, inStart, rootIndex - 1,
        inorderMap
    );

    // 递归构建右子树
    // 右子树的前序遍历范围：从preStart+leftTreeSize+1开始，到preEnd结束
    // 右子树的中序遍历范围：从rootIndex+1开始，到inEnd结束
    root.right = buildTreeHelper(
        preorder, preStart + leftTreeSize + 1, preEnd,
        inorder, rootIndex + 1, inEnd,
        inorderMap
    );

    return root;
}